import java.lang.management.GarbageCollectorMXBean;
import java.util.ArrayList;


public class AlgoritmPrim 
{
	private GrafOrientat graf;
	
	AlgoritmPrim(GrafOrientat graf)
	{
		this.graf = graf;
	}
	
	private boolean test(boolean viz[])
	{
		for(int i=0;i<viz.length;i++)
			if(viz[i] == false)
				return true;
		return false;
	}
	
	public String getArboreMinim()
	{
		int inf=999999999, n=graf.getNrVarfuri() , nincidenta = graf.getNIncidenta();
		
		GrafOrientat g2 = new GrafOrientat();
		
		Muchie [] e = new Muchie[n];
		for(int i=0;i<n;i++)
			e[i] = new Muchie();
		
		int v[] = new int[n];
		v[0] = 0;
		boolean [] viz = new boolean[n];
		for(int i=1;i<n;i++)
			v[i] = inf;
		
		while(test(viz))
		{
			int y , min = inf , poz = -1;
			for(int i=0;i<viz.length;i++)
				if(viz[i] == false)
					if(min > v[i])
						{
							min = v[i];
							poz = i;
						}
			y = poz;
			//System.out.println(y);
			viz[y] = true;
			if(y != 0)
				g2.addListaInc(e[y]);
			
			for(int i=0;i<viz.length;i++)
				{
				//System.out.println("a");
				if(viz[i] == false && graf.cautaInListInc(y, i, true) == true)
					{
					//System.out.println(y+"+"+i);
					if(v[i] > graf.cautaInListInc(y, i))
					
					{
						v[i] = graf.cautaInListInc(y, i);
						e[i].from = y;
						e[i].to = i;
					}
					}
				}
		}
		g2.afisareListaInc();
		return g2.getArboreMinim();
	}
}
